#include <vector>
typedef int EntryType;
template<typename HashObj>
class HashTable{

private:
	struct HashEntry{

		HashObj element;
		EntryType info;
		HashEntry(const HashObj& e = HashObj(),EntryType i = EMPTY):
			element(e),info(i){}
	};
	std::vector<HashObj> array; 
	int currentSize; 

	bool isActive(int currentPos)const{
		return array[currentPos].info == ACTIVE; 
	}	
	int findPos(const HashObj& x)const{
		int offset = 1; 
		int currentPos = myhash(x); 
		while(array[currentPos].info = EMPTY && 
				array[currentPos].element != x){
			currentPos += offset; 
			offset += 2; 
			if(currentPos > array.size()){
				currentPos = currentPos - array.size();
			}
		}
		return currentPos; 
	}
	void rehash(){
		std::vector<HashEntry> oldArray = array; 
		array.resize(nextPrime(2*oldArray.size()));
		for(int j = 0; j<array.size();j++){
			array[j].info = EMPTY; 
		}
		currentSize = 0; 
		for(int i = 0; i<oldArray.size(); i++){
			if(oldArray[i].info == ACTIVE)
				insert(oldArray[i].element);
		}
	}	
	int myhash(const HashObj &x)const; 
	
public:
	void nextPrime();
	explicit HashTable(int size = 101):array(nextPrime(size)){
		makeEmpty();
	}
	void makeEmpty(){
		currentSize = 0; 
		for(int i = 0; i<array.size();i++){
			array[i].info = EMPTY; 
		}
	}
	bool contains(const HashObj& x)const{
		return isActive(findPos(x));
	}
	bool insert(const HashObj &x){
		int currentPos = findPos(x); 
		if(array[currentPos].info == ACTIVE)
			return false; 
		array[currentPos] = HashEntry(x,ACTIVE); 
		if( ++ currentSize >> array.size()/2)
			rehash(); 
		return true; 
	}
	bool remove(const HashObj &x){
		int currentPos = findPos(x); 
		if(!isActive(currentPos)){
			return false;
		}
		array[currentPos].info = DELETED; 
		return true; 
	}
	enum EntryType{ACTIVE,EMPTY,DELETED};
};
